home *** CD-ROM | disk | FTP | other *** search
/ Aminet 21 / Aminet 21 (1997)(GTI - Schatztruhe)[!][Oct 1997].iso / Aminet / gfx / show / gs_src_gs.lha / gs5.03 / gdevddrw.c < prev    next >
C/C++ Source or Header  |  1997-07-10  |  15KB  |  478 lines
  1. /* Copyright (C) 1989, 1995, 1996 Aladdin Enterprises.  All rights reserved.
  2.   
  3.   This file is part of Aladdin Ghostscript.
  4.   
  5.   Aladdin Ghostscript is distributed with NO WARRANTY OF ANY KIND.  No author
  6.   or distributor accepts any responsibility for the consequences of using it,
  7.   or for whether it serves any particular purpose or works at all, unless he
  8.   or she says so in writing.  Refer to the Aladdin Ghostscript Free Public
  9.   License (the "License") for full details.
  10.   
  11.   Every copy of Aladdin Ghostscript must include a copy of the License,
  12.   normally in a plain ASCII text file named PUBLIC.  The License grants you
  13.   the right to copy, modify and redistribute Aladdin Ghostscript, but only
  14.   under certain conditions described in the License.  Among other things, the
  15.   License requires that the copyright notice and this notice be preserved on
  16.   all copies.
  17. */
  18.  
  19. /* gdevddrw.c */
  20. /* Default polygon and image drawing device procedures */
  21. #include "math_.h"
  22. #include "gx.h"
  23. #include "gpcheck.h"
  24. #include "gserrors.h"
  25. #include "gxfixed.h"
  26. #include "gxmatrix.h"
  27. #include "gxdcolor.h"
  28. #include "gxdevice.h"
  29.  
  30. /* ---------------- Polygon and line drawing ---------------- */
  31.  
  32. /* Define the 'remainder' analogue of fixed_mult_quo. */
  33. private fixed
  34. fixed_mult_rem(fixed a, fixed b, fixed c)
  35. {    double prod = (double)a * b;
  36.     return (fixed)(prod - floor(prod / c) * c);
  37. }
  38.  
  39. /*
  40.  * Fill a trapezoid.  Requires:
  41.  *    {left,right}->start.y <= ybot <= ytop <= {left,right}->end.y.
  42.  * Lines where left.x >= right.x will not be drawn.  Thanks to Paul Haeberli
  43.  * for an early floating point version of this algorithm.
  44.  */
  45. typedef struct trap_line_s {
  46.     int di; fixed df;    /* dx/dy ratio = di + df/h */
  47.     fixed ldi, ldf;        /* increment per scan line = ldi + ldf/h */
  48.     fixed x, xf;        /* current value */
  49.     fixed h;
  50. } trap_line;
  51. int
  52. gx_default_fill_trapezoid(gx_device *dev, const gs_fixed_edge *left,
  53.   const gs_fixed_edge *right, fixed ybot, fixed ytop, bool swap_axes,
  54.   const gx_device_color *pdevc, gs_logical_operation_t lop)
  55. {    const fixed ymin = fixed_pixround(ybot) + fixed_half;
  56.     const fixed ymax = fixed_pixround(ytop);
  57.     if ( ymin >= ymax ) return 0;    /* no scan lines to sample */
  58.    {    int iy = fixed2int_var(ymin);
  59.     const int iy1 = fixed2int_var(ymax);
  60.     trap_line l, r;
  61.     int rxl, rxr, ry;
  62.     const fixed
  63.       x0l = left->start.x, x1l = left->end.x,
  64.       x0r = right->start.x, x1r = right->end.x,
  65.       dxl = x1l - x0l, dxr = x1r - x0r;
  66.     const fixed    /* partial pixel offset to first line to sample */
  67.       ysl = ymin - left->start.y,
  68.       ysr = ymin - right->start.y;
  69.     fixed fxl;
  70.     bool fill_direct = color_writes_pure(pdevc, lop);
  71.     gx_color_index cindex;
  72.     dev_proc_fill_rectangle((*fill_rect));
  73.     int max_rect_height = 1;  /* max height to do fill as rectangle */
  74.     int code;
  75.     
  76.     if_debug2('z', "[z]y=[%d,%d]\n", iy, iy1);
  77.  
  78.     if ( fill_direct )
  79.       cindex = pdevc->colors.pure,
  80.       fill_rect = dev_proc(dev, fill_rectangle);
  81.     l.h = left->end.y - left->start.y;
  82.     r.h = right->end.y - right->start.y;
  83.     l.x = x0l + (fixed_half - fixed_epsilon);
  84.     r.x = x0r + (fixed_half - fixed_epsilon);
  85.     ry = iy;
  86.  
  87. #define fill_trap_rect(x,y,w,h)\
  88.   (fill_direct ?\
  89.     (swap_axes ? (*fill_rect)(dev, y, x, h, w, cindex) :\
  90.      (*fill_rect)(dev, x, y, w, h, cindex)) :\
  91.    swap_axes ? gx_fill_rectangle_device_rop(y, x, h, w, pdevc, dev, lop) :\
  92.    gx_fill_rectangle_device_rop(x, y, w, h, pdevc, dev, lop))
  93.  
  94.     /* Compute the dx/dy ratios. */
  95.     /* dx# = dx#i + (dx#f / h#). */
  96. #define compute_dx(tl, d, ys)\
  97.   if ( d >= 0 )\
  98.    { if ( d < tl.h ) tl.di = 0, tl.df = d;\
  99.      else tl.di = (int)(d / tl.h), tl.df = d - tl.di * tl.h,\
  100.        tl.x += ys * tl.di;\
  101.    }\
  102.   else\
  103.    { if ( (tl.df = d + tl.h) >= 0 /* d >= -tl.h */ ) tl.di = -1, tl.x -= ys;\
  104.      else tl.di = (int)-((tl.h - 1 - d) / tl.h), tl.df = d - tl.di * tl.h,\
  105.        tl.x += ys * tl.di;\
  106.    }
  107.  
  108.     /* Compute the x offsets at the first scan line to sample. */
  109.     /* We need to be careful in computing ys# * dx#f {/,%} h# */
  110.     /* because the multiplication may overflow.  We know that */
  111.     /* all the quantities involved are non-negative, and that */
  112.     /* ys# is usually than 1 (as a fixed, of course); this gives us */
  113.     /* a cheap conservative check for overflow in the multiplication. */
  114. #define ymult_limit (max_fixed / fixed_1)
  115. #define ymult_quo(ys, tl)\
  116.   (ys < fixed_1 && tl.df < ymult_limit ? ys * tl.df / tl.h :\
  117.    fixed_mult_quo(ys, tl.df, tl.h))
  118.  
  119.     /*
  120.      * It's worth checking for dxl == dxr, since this is the case
  121.      * for parallelograms (including stroked lines).
  122.      * Also check for left or right vertical edges.
  123.      */
  124.     if ( fixed_floor(l.x) == fixed_pixround(x1l) )
  125.       { /* Left edge is vertical, we don't need to increment. */
  126.         l.di = 0, l.df = 0;
  127.         fxl = 0;
  128.       }
  129.     else
  130.       { compute_dx(l, dxl, ysl);
  131.         fxl = ymult_quo(ysl, l);
  132.         l.x += fxl;
  133.       }
  134.     if ( fixed_floor(r.x) == fixed_pixround(x1r) )
  135.       { /* Right edge is vertical.  If both are vertical, */
  136.         /* we have a rectangle. */
  137.         if ( l.di == 0 && l.df == 0 )
  138.           max_rect_height = max_int;
  139.         else
  140.           r.di = 0, r.df = 0;
  141.       }
  142.     /* The test for fxl != 0 is required because the right edge */
  143.     /* might cross some pixel centers even if the left edge doesn't. */
  144.     else if ( dxr == dxl && fxl != 0 )
  145.        {    if ( l.di == 0 )
  146.           r.di = 0, r.df = l.df;
  147.         else            /* too hard to do adjustments right */
  148.           compute_dx(r, dxr, ysr);
  149.         if ( ysr == ysl && r.h == l.h )
  150.           r.x += fxl;
  151.         else
  152.           r.x += ymult_quo(ysr, r);
  153.        }
  154.     else
  155.        {    compute_dx(r, dxr, ysr);
  156.         r.x += ymult_quo(ysr, r);
  157.        }
  158.     rxl = fixed2int_var(l.x);
  159.     rxr = fixed2int_var(r.x);
  160.  
  161.     /*
  162.      * Take a shortcut if we're only sampling a single scan line,
  163.      * or if we have a rectangle.
  164.      */
  165.     if ( iy1 - iy <= max_rect_height )
  166.        {    iy = iy1;
  167.         if_debug2('z', "[z]rectangle, x=[%d,%d]\n", rxl, rxr);
  168.         goto last;
  169.        }
  170.  
  171.     /* Compute one line's worth of dx/dy. */
  172.     /* dx# * fixed_1 = ld#i + (ld#f / h#). */
  173. #define compute_ldx(tl, ys)\
  174.   if ( tl.df < ymult_limit )\
  175.     { if ( tl.df == 0 )    /* vertical edge, worth checking for */\
  176.     tl.ldi = int2fixed(tl.di),\
  177.     tl.ldf = 0,\
  178.     tl.xf = -tl.h;\
  179.       else\
  180.     tl.ldi = int2fixed(tl.di) + int2fixed(tl.df) / tl.h,\
  181.     tl.ldf = int2fixed(tl.df) % tl.h,\
  182.     tl.xf = (ys < fixed_1 ? ys * tl.df % tl.h :\
  183.          fixed_mult_rem(ys, tl.df, tl.h)) - tl.h;\
  184.     }\
  185.   else\
  186.     tl.ldi = int2fixed(tl.di) + fixed_mult_quo(fixed_1, tl.df, tl.h),\
  187.     tl.ldf = fixed_mult_rem(fixed_1, tl.df, tl.h),\
  188.     tl.xf = fixed_mult_rem(ys, tl.df, tl.h) - tl.h
  189.     compute_ldx(l, ysl);
  190.     if ( dxr == dxl && ysr == ysl && r.h == l.h )
  191.       r.ldi = l.ldi, r.ldf = l.ldf, r.xf = l.xf;
  192.     else
  193.       { compute_ldx(r, ysr);
  194.       }
  195. #undef compute_ldx
  196.  
  197.     while ( ++iy != iy1 )
  198.        {    int ixl, ixr;
  199. #define step_line(tl)\
  200.   tl.x += tl.ldi;\
  201.   if ( (tl.xf += tl.ldf) >= 0 ) tl.xf -= tl.h, tl.x++;
  202.         step_line(l);
  203.         step_line(r);
  204. #undef step_line
  205.         ixl = fixed2int_var(l.x);
  206.         ixr = fixed2int_var(r.x);
  207.         if ( ixl != rxl || ixr != rxr )
  208.            {    code = fill_trap_rect(rxl, ry, rxr - rxl, iy - ry);
  209.             if ( code < 0 ) goto xit;
  210.             rxl = ixl, rxr = ixr, ry = iy;
  211.            }    
  212.        }
  213. last:    code = fill_trap_rect(rxl, ry, rxr - rxl, iy - ry);
  214. xit:    if ( code < 0 && fill_direct )
  215.       return_error(code);
  216.     return_if_interrupt();
  217.     return code;
  218.    }
  219. }
  220.  
  221. /* Fill a parallelogram whose points are p, p+a, p+b, and p+a+b. */
  222. /* We should swap axes to get best accuracy, but we don't. */
  223. /* We must be very careful to follow the center-of-pixel rule in all cases. */
  224. int
  225. gx_default_fill_parallelogram(gx_device *dev,
  226.   fixed px, fixed py, fixed ax, fixed ay, fixed bx, fixed by,
  227.   const gx_device_color *pdevc, gs_logical_operation_t lop)
  228. {    fixed t;
  229.     fixed qx, qy, ym;
  230.     dev_proc_fill_trapezoid((*fill_trapezoid));
  231.     gs_fixed_edge left, right;
  232.     int code;
  233.  
  234.     /* Ensure ay >= 0, by >= 0. */
  235.     if ( ay < 0 )
  236.       px += ax, py += ay, ax = -ax, ay = -ay;
  237.     if ( by < 0 )
  238.       px += bx, py += by, bx = -bx, by = -by;
  239.     qx = px + ax + bx;
  240.     /* Make a special fast check for rectangles. */
  241.     if ( (ay | bx) == 0 || (by | ax) == 0 )
  242.     {    /* If a point falls exactly on the middle of a pixel, */
  243.         /* we must round it down, not up. */
  244.         int rx = fixed2int_pixround(px);
  245.         int ry = fixed2int_pixround(py);
  246.         /* Exactly one of (ax,bx) and one of (ay,by) is non-zero. */
  247.         int w = fixed2int_pixround(qx) - rx;
  248.         if ( w < 0 ) rx += w, w = -w;
  249.         return gx_fill_rectangle_device_rop(rx, ry, w,
  250.             fixed2int_pixround(py + ay + by) - ry,
  251.             pdevc, dev, lop);
  252.     }
  253.     /*
  254.      * Not a rectangle.  Ensure that the 'a' line is to the left of
  255.      * the 'b' line.  Testing ax <= bx is neither sufficient nor
  256.      * necessary: in general, we need to compare the slopes.
  257.      */
  258. #define swap(r, s) (t = r, r = s, s = t)
  259.     if ( (ax ^ bx) < 0 )
  260.       { /* In this case, the test ax <= bx is sufficient. */
  261.         if ( ax > bx )
  262.           swap(ax, bx), swap(ay, by);
  263.       }
  264.     else
  265.       { /*
  266.          * Compare the slopes.  We know that ay >= 0, by >= 0,
  267.          * and ax and bx have the same sign; the lines are in the
  268.          * correct order iff
  269.          *        ay/ax >= by/bx, or
  270.          *        ay*bx >= by*ax
  271.          * Eventually we can probably find a better way to test this,
  272.          * without using floating point.
  273.          */
  274.         if ( (double)ay * bx < (double)by * ax )
  275.           swap(ax, bx), swap(ay, by);
  276.       }
  277.     fill_trapezoid = dev_proc(dev, fill_trapezoid);
  278.     qy = py + ay + by;
  279.     left.start.x = right.start.x = px;
  280.     left.start.y = right.start.y = py;
  281.     left.end.x = px + ax;
  282.     left.end.y = py + ay;
  283.     right.end.x = px + bx;
  284.     right.end.y = py + by;
  285. #define rounded_same(p1, p2)\
  286.   (fixed_pixround(p1) == fixed_pixround(p2))
  287.     if ( ay < by )
  288.       { if ( !rounded_same(py, left.end.y) )
  289.           { code = (*fill_trapezoid)(dev, &left, &right, py, left.end.y,
  290.                      false, pdevc, lop);
  291.             if ( code < 0 )
  292.           return code;
  293.           }
  294.         left.start = left.end;
  295.         left.end.x = qx, left.end.y = qy;
  296.         ym = right.end.y;
  297.         if ( !rounded_same(left.start.y, ym) )
  298.           { code = (*fill_trapezoid)(dev, &left, &right, left.start.y, ym,
  299.                      false, pdevc, lop);
  300.             if ( code < 0 )
  301.           return code;
  302.           }
  303.         right.start = right.end;
  304.         right.end.x = qx, right.end.y = qy;
  305.       }
  306.     else
  307.       { if ( !rounded_same(py, right.end.y) )
  308.           { code = (*fill_trapezoid)(dev, &left, &right, py, right.end.y,
  309.                      false, pdevc, lop);
  310.             if ( code < 0 )
  311.           return code;
  312.           }
  313.         right.start = right.end;
  314.         right.end.x = qx, right.end.y = qy;
  315.         ym = left.end.y;
  316.         if ( !rounded_same(right.start.y, ym) )
  317.           { code = (*fill_trapezoid)(dev, &left, &right, right.start.y, ym,
  318.                      false, pdevc, lop);
  319.             if ( code < 0 )
  320.           return code;
  321.           }
  322.         left.start = left.end;
  323.         left.end.x = qx, left.end.y = qy;
  324.       }
  325.     if ( !rounded_same(ym, qy) )
  326.       return (*fill_trapezoid)(dev, &left, &right, ym, qy,
  327.                    false, pdevc, lop);
  328.     else
  329.       return 0;
  330. #undef rounded_same
  331. #undef swap
  332. }
  333.  
  334. /* Fill a triangle whose points are p, p+a, and p+b. */
  335. /* We should swap axes to get best accuracy, but we don't. */
  336. int
  337. gx_default_fill_triangle(gx_device *dev,
  338.   fixed px, fixed py, fixed ax, fixed ay, fixed bx, fixed by,
  339.   const gx_device_color *pdevc, gs_logical_operation_t lop)
  340. {    fixed t;
  341.     fixed ym;
  342.     dev_proc_fill_trapezoid((*fill_trapezoid)) =
  343.       dev_proc(dev, fill_trapezoid);
  344.     gs_fixed_edge left, right;
  345.     int code;
  346.  
  347.     /* Ensure ay >= 0, by >= 0. */
  348.     if ( ay < 0 )
  349.       px += ax, py += ay, bx -= ax, by -= ay, ax = -ax, ay = -ay;
  350.     if ( by < 0 )
  351.       px += bx, py += by, ax -= bx, ay -= by, bx = -bx, by = -by;
  352.     /* Ensure ay <= by. */
  353. #define swap(r, s) (t = r, r = s, s = t)
  354.     if ( ay > by )
  355.       swap(ax, bx), swap(ay, by);
  356. #undef swap
  357.     /*
  358.      * Make a special check for a flat bottom or top,
  359.      * which we can handle with a single call on fill_trapezoid.
  360.      */
  361.     left.start.x = right.start.x = px;
  362.     left.start.y = right.start.y = py;
  363.     if ( ay == 0 ) {
  364.       /* Flat top */
  365.       if ( ax < 0 )
  366.         left.start.x = px + ax;
  367.       else
  368.         right.start.x = px + ax;
  369.       left.end.x = right.end.x = px + bx;
  370.       left.end.y = right.end.y = py + by;
  371.       ym = py;
  372.     } else if ( ay == by ) {
  373.       /* Flat bottom */
  374.       if ( ax < bx )
  375.         left.end.x = px + ax, right.end.x = px + bx;
  376.       else
  377.         left.end.x = px + bx, right.end.x = px + ax;
  378.       left.end.y = right.end.y = py + by;
  379.       ym = py;
  380.     } else {
  381.       ym = py + ay;
  382.       if ( fixed_mult_quo(bx, ay, by) < ax ) {
  383.         /* The 'b' line is to the left of the 'a' line. */
  384.         left.end.x = px + bx, left.end.y = py + by;
  385.         right.end.x = px + ax, right.end.y = py + ay;
  386.         code = (*fill_trapezoid)(dev, &left, &right, py, ym,
  387.                      false, pdevc, lop);
  388.         right.start = right.end;
  389.         right.end = left.end;
  390.       } else {
  391.         /* The 'a' line is to the left of the 'b' line. */
  392.         left.end.x = px + ax, left.end.y = py + ay;
  393.         right.end.x = px + bx, right.end.y = py + by;
  394.         code = (*fill_trapezoid)(dev, &left, &right, py, ym,
  395.                      false, pdevc, lop);
  396.         left.start = left.end;
  397.         left.end = right.end;
  398.       }
  399.       if ( code < 0 )
  400.         return code;
  401.     }
  402.     return (*fill_trapezoid)(dev, &left, &right, ym, right.end.y,
  403.                  false, pdevc, lop);
  404. }
  405.  
  406. /* Draw a one-pixel-wide line. */
  407. int
  408. gx_default_draw_thin_line(gx_device *dev,
  409.   fixed fx0, fixed fy0, fixed fx1, fixed fy1,
  410.   const gx_device_color *pdevc, gs_logical_operation_t lop)
  411. {    int ix = fixed2int_var(fx0);
  412.     int iy = fixed2int_var(fy0);
  413.     int itox = fixed2int_var(fx1);
  414.     int itoy = fixed2int_var(fy1);
  415.  
  416.     return_if_interrupt();
  417.     if ( itoy == iy )        /* horizontal line */
  418.       { return (ix <= itox ?
  419.             gx_fill_rectangle_device_rop(ix, iy, itox - ix + 1, 1,
  420.                          pdevc, dev, lop) :
  421.             gx_fill_rectangle_device_rop(itox, iy, ix - itox + 1, 1,
  422.                          pdevc, dev, lop)
  423.             );
  424.       }
  425.     if ( itox == ix )        /* vertical line */
  426.       { return (iy <= itoy ?
  427.             gx_fill_rectangle_device_rop(ix, iy, 1, itoy - iy + 1,
  428.                          pdevc, dev, lop) :
  429.             gx_fill_rectangle_device_rop(ix, itoy, 1, iy - itoy + 1,
  430.                          pdevc, dev, lop)
  431.             );
  432.       }
  433.     if ( color_writes_pure(pdevc, lop) &&
  434.          (*dev_proc(dev, draw_line))(dev, ix, iy, itox, itoy,
  435.                      pdevc->colors.pure) >= 0
  436.        )
  437.       return 0;
  438.     { fixed h = fy1 - fy0;
  439.       fixed w = fx1 - fx0;
  440.       fixed tf;
  441.       bool swap_axes;
  442.       gs_fixed_edge left, right;
  443.  
  444. #define fswap(a, b) tf = a, a = b, b = tf
  445.       if ( (w < 0 ? -w : w) <= (h < 0 ? -h : h) )
  446.         { if ( h < 0 )
  447.         fswap(fx0, fx1), fswap(fy0, fy1),
  448.         h = -h;
  449.           right.start.x = (left.start.x = fx0 - fixed_half) + fixed_1;
  450.           right.end.x = (left.end.x = fx1 - fixed_half) + fixed_1;
  451.           left.start.y = right.start.y = fy0;
  452.           left.end.y = right.end.y = fy1;
  453.           swap_axes = false;
  454.         }
  455.       else
  456.         { if ( w < 0 )
  457.         fswap(fx0, fx1), fswap(fy0, fy1),
  458.         w = -w;
  459.           right.start.x = (left.start.x = fy0 - fixed_half) + fixed_1;
  460.           right.end.x = (left.end.x = fy1 - fixed_half) + fixed_1;
  461.           left.start.y = right.start.y = fx0;
  462.           left.end.y = right.end.y = fx1;
  463.           swap_axes = true;
  464.         }
  465.       return (*dev_proc(dev, fill_trapezoid))(dev, &left, &right,
  466.                           left.start.y, left.end.y,
  467.                           swap_axes, pdevc, lop);
  468. #undef fswap
  469.     }
  470. }
  471.  
  472. /* Stub out the obsolete procedure. */
  473. int
  474. gx_default_draw_line(gx_device *dev,
  475.   int x0, int y0, int x1, int y1, gx_color_index color)
  476. {    return -1;
  477. }
  478.